<head>
    <meta charset="UTF-8">
<title>算法提高 JOE的算数</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
有一天，JOE终于不能忍受计算a^b%c这种平凡的运算了。所以他决定要求你写一个程序，计算a^b%c。</p>
<p>&nbsp;</p>
<p>提示：若b为奇数,，a^b=(a^(b/2))^2*a，否则a^b=(a^(b/2))^2。<br />
【输入格式】　　<span class="Apple-tab-span" style="white-space: pre"> </span></p>
<p>　　 三个非负整数a,b,c；</p>
<p>【输出格式】</p>
<p>一个整数ans，表示a^b%c；</p>
<p>【样例输入】</p>
<p>7 2 5<span class="Apple-tab-span" style="white-space: pre"> </span></p>
<p>【样例输出】</p>
<p>4</p>
<p>【数据规模和约定】</p>
<p>30% a &lt;= 100, b &lt;= 10^4, 1 &lt;= c &lt;= 100</p>
<p>60% a &lt;=10^4, b &lt;= 10^5, 1 &lt;= c &lt;= 10^4</p>
<p>100% a &lt;=10^6, b &lt;= 10^9, 1 &lt;= c &lt;= 10^6</p>